public class Sort {
    //直接插入排序
    //时间复杂度最坏情况下：O(n^2)，最好情况下O(n)
    //空间复杂度O（1），没有重新申请数据
    //稳定
    public static void insertSort(int[] array) {
        for (int i = 0; i < array.length ; i++) {
            int tmp=array[i];
            int j=i-1;
            for (; j >=0; j--) {
                if(array[j]>tmp){//array[j]>tmp加不加=符号和稳定有关系
                    //本身是一个稳定的排序可以实现为不稳定的排序
                    //本身一个不稳定的排序是不可能变成一个稳定排序的
                    array[j+1]=array[j];
                }else{
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }



    //希尔排序
    public static void shellSort(int array[]) {
        int gap=array.length;
        while(gap>1){
            gap/=2;
            shell(array,gap);
        }
    }

    public static void shell(int[] array,int gap) {
        for (int i = gap; i < array.length ; i++) {
            int tmp=array[i];
            int j=i-gap;
            for (; j >=0; j-=gap) {
                if(array[j]>tmp){//array[j]>tmp加不加=符号和稳定有关系
                    //本身是一个稳定的排序可以实现为不稳定的排序
                    //本身一个不稳定的排序是不可能变成一个稳定排序的
                    array[j+gap]=array[j];
                }else{
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

    //直接选择排序
    //时间复杂度 O(N^2)
    //空间复杂度 o(1)
    //稳定性：不稳定
    public static void swap(int[] array,int i,int j) {
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex=i;
            for (int j = i+1; j < array.length ; j++) {
               if(array[j]<array[minIndex]){
                   minIndex=j;
               }
            }
            swap(array,i,minIndex);
        }
    }

    public static void selectSort2(int[] array) {
        int left=0;
        int right= array.length-1;
        while(left<right){
            int minIndex=left;
            int maxIndex=right;
            for (int i = left+1; i <=right; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                }
                if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
                swap(array, minIndex, left);
                if (maxIndex == left) {
                    //防止第一个是也是最大值，如果和最小值一换，最大值就跑到了原来最小值的位置
                    maxIndex = minIndex;
                }
            }
            swap(array,maxIndex,right);
            left++;
            right--;
        }
    }

    //创建大根堆
    private static void creatHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >=0; parent--) {
            siftDown(array,parent,array.length);
        }
    }

    private static void siftDown(int[] array,int parent, int length) {
        int child=2*parent+1;
        while(child<length){
            if(child+1<length&&array[child]<array[child+1]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array, child,parent);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }
    }

    //堆排序
    //时间复杂度O(N*logN)
    //空间复杂度:O(1) 没有递归也没有申请更多内存
    //稳定性：不稳定
    public static void heapSort(int[] array) {
        creatHeap(array);
        int end= array.length-1;
        while(end>0){
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }
    }

    //冒泡排序
    //时间复杂度O(n^2)
    //如果加了优化boolean flg=false;这部分最好情况是O(n)
    //空间复杂度O（1）
    //稳定性 稳定
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length ; i++) {
            boolean flg=false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg=true;
                }
            }
            if(!flg){
                break;
            }
        }

    }
}
